We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only.

[…] redaktorom udała się rzecz dość rzadka w tego typu publikacjach, mianowicie stworzyli imponujących rozmiarów księgę pamiątkową, która jednak, poza walorami okolicznościowymi, charakteryzuje się wysokim poziomem naukowym i zawiera sporo oryginalnych, wartościowych treści, z konieczności prezentowanych w krótkich formach, co jednak nie obniża ich rangi teoretycznej. Ponadto […] udało się w tej publikacji zgromadzić bardzo liczne, a jednocześnie reprezentatywne grono najwybitniejszych polskich filozofów, którzy ofiarowali profesorowi Tyburskiemu swoje cenne teksty, co czyni tę książkę tym bardziej wartościową i spowoduje, jak można (...) przypuszczać, że jeszcze po wielu latach będzie się do niej sięgało jako o źródła oryginalnych i bardzo ciekawych przemyśleń. Prof. dr hab. Jarosław Rolewski. (shrink)